package com.zack.algorithm;

/**
 * email: miao.du@shuruitech.com author: zack time(default is Create Time may
 * change)：Apr 6, 2017 10:50:35 AM
 **/

public class FindK {

    public static void main(String[] args) {
        new FindK().findK();
    }

    public void findK() {
        int[] arr = new int[] { 3, 2, 7, 8, 1, 6, 5, 4, 11, 21, 12, 13, 67 };
        System.out.println(toTestOrder(arr, 0, arr.length - 1, 10));
    }

    public int toTestOrder(int arr[], int left, int right, int findK) {

        int leftPoint = left;
        int rightPoint = right;
        int base = arr[leftPoint];
        if (left < right) {
            while (true) {
                while (leftPoint < rightPoint && arr[leftPoint] < base) {
                    leftPoint++;
                }
                while (rightPoint > leftPoint && arr[rightPoint] > base) {
                    rightPoint--;
                }
                if (leftPoint < rightPoint) {
                    if (arr[rightPoint] == arr[leftPoint]) {
                        leftPoint++;
                    } else {
                        swap(arr, rightPoint, leftPoint);
                    }
                } else {
                    break;
                }
            }
            if (findK < leftPoint) {
                return toTestOrder(arr, left, leftPoint - 1, findK);
            } else if (findK > rightPoint) {
                return toTestOrder(arr, leftPoint + 1, right, findK);
            } else {
                return arr[leftPoint - 1];
            }
        } else {
            return Integer.MIN_VALUE;
        }
    }

    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

}
